#pragma region  【算法5 - 11】求单源点到图上其余各顶点的最短路径-- - Dijkstra 算法 
void ShortestPath(MGraph *G, int P[N], float D[N])
{ //设源点为顶点0，求到其余顶点的最短路径
    // D[v]存放从源点顶点0到终点v最短路径其长度
    // P[v]存放相应的最短路径终点的前驱点
    //常量INFINITY是为邻接矩阵中的∞
    int final[N] = {1, 0};
    for (i = 0; i < N; i++)
    {
        D[i] = G->edges[0][i];
        P[i] = 0;
    }
    D[0] = 0;
    final[0] = 1;
    P[0] = -1; //初始化，源点属于S集
    for (i = 1; i < N; i++)
    {
        //开始主循环，每次求得源点到某个顶点k的最短路径，并加k到S集
        min = INFINITY + 1;     //为了将没有路径的点最后选中，初始化∞+1
        for (k = 0; k < N; k++) //从未进入S的点中找最小的D[k]
            if (final[k] == 0 && D[k] < min)
            //顶点k没进入S中且当前的路径更短
            {
                j = k; //具有更小路径的点存储在j中
                min = D[k];
            }
        final[j] = 1; //将j加入S集合
        for (k = 0; k < N; k++)
            //更新其它没进入S的点的当前最短路径及长度
            if (final[k] == 0 && (D[j] + G->edges[j][k] < D[k]))
            //对 k∈V-S的点
            {
                D[k] = D[j] + G->edges[j][k];
                //将 D[k]修改为更短路径长度
                P[k] = j;
                //记忆对应的路径，将k的前驱结点改为j
            }
    }
    for (i = 1; i < N; i++)
    //输出各最短路径的长度及路径上的结点
    {
        printf("%f：%d", D[i], i);
        pre = P[i];
        while (pre >= 0)
        {
            printf("←%d", pre);
            pre = P[pre];
        }
        printf("\n");
    }
}
#pragma endregion